1116. 打印零与奇偶数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 信号量

1. 📝 题目描述

• leetcode

现有函数 printNumber 可以用一个整数参数调用，并输出该整数到控制台。

• 例如，调用 printNumber(7) 将会输出 7 到控制台。

给你类 ZeroEvenOdd 的一个实例，该类中有三个函数：zero、even 和 odd。ZeroEvenOdd 的相同实例将会传递给三个不同线程：

• 线程 A：调用 zero()，只输出 0
• 线程 B：调用 even()，只输出偶数
• 线程 C：调用 odd()，只输出奇数

修改给出的类，以输出序列 "010203040506..."，其中序列的长度必须为 2n。

实现 ZeroEvenOdd 类：

• ZeroEvenOdd(int n) 用数字 n 初始化对象，表示需要输出的数。
• void zero(printNumber) 调用 printNumber 以输出一个 0。
• void even(printNumber) 调用printNumber 以输出偶数。
• void odd(printNumber) 调用 printNumber 以输出奇数。

---

示例 1：

输入：n = 2
输出："0102"
解释：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。

示例 2：

输入：n = 5
输出："0102030405"

---

提示：

• 1 <= n <= 1000

2. 🎯 s.1 - 信号量

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

// JavaScript 无原生线程支持，使用 Promise 模拟
class ZeroEvenOdd {
  constructor(n) {
    this.n = n
    this.state = 0 // 0: print zero, 1: print odd, 2: print even
    this.resolve = null
    this.promise = new Promise((r) => (this.resolve = r))
  }

  async zero(printNumber) {
    for (let i = 1; i <= this.n; i++) {
      while (this.state !== 0) await this.promise
      printNumber(0)
      this.state = i % 2 === 1 ? 1 : 2
      const old = this.resolve
      this.promise = new Promise((r) => (this.resolve = r))
      old()
    }
  }

  async odd(printNumber) {
    for (let i = 1; i <= this.n; i += 2) {
      while (this.state !== 1) await this.promise
      printNumber(i)
      this.state = 0
      const old = this.resolve
      this.promise = new Promise((r) => (this.resolve = r))
      old()
    }
  }

  async even(printNumber) {
    for (let i = 2; i <= this.n; i += 2) {
      while (this.state !== 2) await this.promise
      printNumber(i)
      this.state = 0
      const old = this.resolve
      this.promise = new Promise((r) => (this.resolve = r))
      old()
    }
  }
}

• 时间复杂度：$O(n)$，循环 n 次
• 空间复杂度：$O(1)$，只使用常数级别的同步原语

算法思路：

• 使用三个信号量分别控制 zero、odd、even 的执行时机
• zero 每次打印后根据当前轮次决定释放 odd 或 even 的信号量
• odd/even 打印完后释放 zero 的信号量，形成交替循环